MST Lab: Step 2 - The Core Algorithm

Now we run the main loop of Prim's. We do this `N` times to add all `N` planets to the MST.

Guidance for Step 2

a) Find `u`: In each iteration, loop from `v = 0` to `N-1` to find the planet `u` that has the smallest `key[v]` and is not yet in the MST (`in_mst[v]` is `False`).
b) Add `u` to MST: Mark the chosen planet `u` as being in the MST by setting `in_mst[u] = True`.
c) Update Neighbors: Loop through all other planets `v` from `0` to `N-1`.
Check `v`: If `v` is not in the MST, calculate the `distance` from `u` to `v`.
Update `key`: If this `distance` is less than `key[v]`, it means we found a *cheaper way* to connect `v`. Update `key[v] = distance` and set `parent[v] = u`.

# The algorithm must run N times to add all N planets
for _ in range(N):
    
    # a) Find the planet 'u' with the smallest key
    #    that is not yet in the MST.
    min_key_value = float('inf')
    u = -1
    for v in range(N):
        # Find the cheapest node 'v' that is not in the MST
        if ____ and ____ < min_key_value:
            min_key_value = key[v]
            u = v
            
    # b) Add this minimum-cost planet 'u' to the MST
    in_mst[u] = ____

    # c) Now, update the 'key' and 'parent' for all
    #    neighbors 'v' of 'u'.
    for v in range(N):
        # Only update planets 'v' that are NOT in the MST
        if ____:
            # Get the cost to build a lane from u to v
            distance = get_distance(planets[u], planets[v])
            
            # If this new lane is cheaper than the
            # *current* best way to reach 'v'
            if distance ____:
                # Update the new best cost and parent
                ____ = distance
                ____ = u

Copied!